package com.jhy.review.day02;

import com.jhy.review.day01.Node;

/**
 * 求第一个汇聚的点就是最低公共祖先
 * 求两个节点的最低公共祖先
 *第二种解法 lca有以下两大类
 * 1)o1是o2的lca、或者o2是o1的lca
 * 2)o1与o2不互为lca，要往上面找才能找到
 *
 * 时间复杂度为O（k）
 */
public class LowestCommonAncestor2 {

    public static Node lca(Node head, Node o1, Node o2){
        // 遇到o1和o2就放回o1或者o2。
        if(head == null || head == o1 || head == o2){
            // base case
            return head;
        }
        // 要判断当前节点的状态 来放回值
        Node left = lca(head.left, o1, o2);
        Node right = lca(head.right, o1, o2);

        // 左右都不空 就放回当前值
        if(left != null && right != null){
            return head;
        }
        // 左右两颗树 并不都有放回值
        return  left != null ? left : right;
    }
}
